#![allow(dead_code)]
use std::cell::RefCell;
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
use std::fmt::{Display, Formatter, Result};
use std::ops::Drop;
use std::rc::Rc;

#[derive(Debug)]
struct RefNode(Rc<RefCell<TrieNode>>);
impl RefNode {
    fn new() -> Self {
        Self(Rc::new(RefCell::new(TrieNode::new())))
    }

    fn delete(&mut self, s: &str) {
        if self.search(s) == 0 {
            println!("未加入过字符串{}，直接退出", s);
            return;
        }
        let mut node: RefNode = RefNode(self.0.clone());
        node.0.borrow_mut().pass -= 1;
        for c in s.chars() {
            let next = node.0.borrow().nexts.get(&c).unwrap().0.clone();
            next.borrow_mut().pass -= 1;
            if next.borrow().pass == 0 {
                println!(
                    ">>> 节点TrieNode[p={}, e={}]引用次数-1",
                    next.borrow().pass,
                    next.borrow().end
                );
                node.0.borrow_mut().nexts.remove(&c);
                return;
            }

            node = RefNode(next);
        }
        node.0.borrow_mut().end -= 1;
    }

    fn insert(&self, s: &str) {
        let mut node: RefNode = RefNode(self.0.clone());
        node.0.borrow_mut().pass += 1;
        s.chars().for_each(|c| {
            let next = RefNode(
                node.0
                    .borrow_mut()
                    .nexts
                    .entry(c)
                    .or_insert(RefNode::new())
                    .0
                    .clone(),
            );
            next.0.borrow_mut().pass += 1;
            node = next;
        });
        node.0.borrow_mut().end += 1;
    }

    /* 查询一个字符串加入了多少次 */
    fn search(&self, s: &str) -> u32 {
        if s == "" {
            return self.0.borrow().end;
        }

        let mut node: RefNode = RefNode(self.0.clone());
        for c in s.chars() {
            if node.0.borrow().nexts.get(&c).is_none() {
                return 0;
            }
            let next = node.0.borrow().nexts.get(&c).unwrap().0.clone();
            node = RefNode(next);
        }

        let x = node.0.borrow().end;
        x
    }

    fn prefix_num(&self, s: &str) -> u32 {
        if s == "" {
            return self.0.borrow().pass;
        }
        let mut node = RefNode(self.0.clone());
        for c in s.chars() {
            if node.0.borrow().nexts.get(&c).is_none() {
                return 0;
            }
            let next = node.0.borrow().nexts.get(&c).unwrap().0.clone();
            node = RefNode(next);
        }

        let x = node.0.borrow().pass;
        x
    }
}

#[derive(Debug)]
struct TrieNode {
    pass: u32,
    end: u32,
    nexts: HashMap<char, RefNode>,
}
impl Drop for TrieNode {
    fn drop(&mut self) {
        println!("析构TrieNode[p={}, e={}]", self.pass, self.end);
    }
}
impl TrieNode {
    fn new() -> Self {
        Self {
            pass: 0,
            end: 0,
            nexts: HashMap::new(),
        }
    }
}
impl Display for TrieNode {
    fn fmt(&self, f: &mut Formatter) -> Result {
        writeln!(f, "Node[p:{}, e: {}]", self.pass, self.end)
    }
}

fn print_trie(trie: &RefNode) {
    print!("{}", trie.0.borrow());
    trie.0.borrow().nexts.iter().for_each(|(road, next)| {
        print!(" -{}-> ", road);
        print_trie(next);
    });
}

pub fn test_trienode() {
    let root = RefNode::new();
    let s = vec!["", "abc", "abc", "bck", "abd", "ace"];
    println!("=========== 前缀树 ===========");
    println!("字符串：{:?}", s);
    println!("前缀树：");
    s.iter().for_each(|&string| root.insert(string));
    print_trie(&root);

    println!("字符串：{:?}", s);
    println!("查询字符串加入的次数：");
    ["", "bck", "abc", "bcke"]
        .iter()
        .for_each(|s| println!("root.contains({}): {}次", s, root.search(s)));

    println!("字符串：{:?}", s);
    println!("查询字符串作为前缀的次数：");
    ["", "bck", "ab", "a"]
        .iter()
        .for_each(|s| println!("root.contains({}): 作为前缀{}次", s, root.prefix_num(s)));

    let s = vec!["abc", "abc", "abc"];
    let mut root = RefNode::new();
    println!("=========== 前缀树 ===========");
    s.iter().for_each(|&string| root.insert(string));
    println!("字符串：{:?}", s);
    println!("前缀树：");
    print_trie(&root);

    println!("字符串：{:?}", s);
    print_trie(&root);
    ["", "abc", "abc", "abc"].iter().for_each(|s| {
        println!("删除字符串：{}", s);
        root.delete(s);
        print_trie(&root);
    });

    println!("==================函数的最后================");
}

struct Program {
    start: u32,
    end: u32,
}
impl Program {
    fn new(start: u32, end: u32) -> Self {
        Self { start, end }
    }
}
impl Ord for Program {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.end.cmp(&other.end)
    }
}
impl PartialOrd for Program {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
impl PartialEq for Program {
    fn eq(&self, other: &Self) -> bool {
        self.end == other.end
    }
}
impl Eq for Program {}
impl Display for Program {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        write!(f, "会议[{}-{}]", self.start, self.end)
    }
}

fn best_arrange(programs: &mut Vec<Program>, timepoint: u32) -> u32 {
    programs.sort();
    let mut res = 0u32;
    let mut timepoint = timepoint;
    programs.iter().for_each(|p| {
        if timepoint <= p.start {
            res += 1;
            timepoint = p.end;
        }
    });
    res
}

fn less_money(arr: &Vec<i32>) -> i32 {
    let mut min_heap = BinaryHeap::new();
    arr.iter().for_each(|l| min_heap.push(*l));
    let mut sum = 0;
    while min_heap.len() > 1 {
        sum += min_heap.pop().unwrap() + min_heap.pop().unwrap();
        min_heap.push(sum);
    }
    sum
}

fn middle(nums: Vec<i32>) -> f32 {
    let mut min_heap = BinaryHeap::new();
    let mut max_heap = BinaryHeap::new();
    max_heap.push(nums[0]);

    nums[1..].iter().for_each(|num| {
        if num <= max_heap.peek().unwrap() {
            max_heap.push(*num);
        } else {
            min_heap.push(Reverse(*num));
        }
        if max_heap.len() + 2 == min_heap.len() {
            let Reverse(num) = min_heap.pop().unwrap();
            max_heap.push(num);
        } else if min_heap.len() + 2 == max_heap.len() {
            min_heap.push(Reverse(max_heap.pop().unwrap()))
        }
    });
    if nums.len() % 2 == 0 {
        return *max_heap.peek().unwrap() as f32;
    } else {
        let m1 = *max_heap.peek().unwrap();
        let Reverse(m2) = min_heap.peek().unwrap();
        return (m1 as f32 + *m2 as f32) / 2.0;
    }
}

fn queen_is_valid(record: &mut Vec<usize>, line: usize, row: usize) -> bool {
    for line_fixed in 0..line {
        if record[line_fixed] == row
            || (record[line_fixed] as i32 - row as i32).abs()
                == (line_fixed as i32 - line as i32).abs()
        {
            return false;
        }
    }
    true
}

fn queen_pos(line: usize, record: &mut Vec<usize>, n: usize) -> u32 {
    if line == n {
        return 1;
    }
    let mut res: u32 = 0;
    for cow in 0..n {
        if queen_is_valid(record, line, cow) {
            record[line] = cow;
            res += queen_pos(line + 1, record, n);
        }
    }
    res
}

fn nqueens(num: usize) -> u32 {
    let mut record: Vec<usize> = vec![0; num];
    let res = queen_pos(0, &mut record, num);
    res
}

pub fn test_greedy() {
    let mut programs = vec![
        Program::new(6, 7),
        Program::new(6, 9),
        Program::new(7, 10),
        Program::new(9, 11),
        Program::new(8, 12),
        Program::new(10, 13),
    ];
    programs.iter().for_each(|p| print!("{}, ", p));
    println!("");
    let res = best_arrange(&mut programs, 6);
    println!("最多可安排[{}]个会议", res);

    let v = vec![5, 3, 7, 4];
    println!("数据流:{:?}", v);
    let res = middle(v);
    println!("中位数：{}", res);

    let num = 1;
    let res = nqueens(num);
    println!("{}x{}的棋盘放{}个皇后有{}种摆法", num, num, num, res);
    let num = 2;
    let res = nqueens(num);
    println!("{}x{}的棋盘放{}个皇后有{}种摆法", num, num, num, res);
    let num = 3;
    let res = nqueens(num);
    println!("{}x{}的棋盘放{}个皇后有{}种摆法", num, num, num, res);
    let num = 8;
    let res = nqueens(num);
    println!("{}x{}的棋盘放{}个皇后有{}种摆法", num, num, num, res);
}
